/**
 * 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。
 * 在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。
 * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
 */
class MaxArea {

    public static void main(String[] args) {
        System.out.println(MaxArea.maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7}));
    }

    /**
     * 这个方法值只是优化了一半，还是需要两个循环
     *
     * @param height
     * @return
     */
    public static int maxAreaBad(int[] height) {
        //初始化最大值
        int area = 0;
        //第一个循环从前遍历
        for (int i = 0; i < height.length; i++) {
            //第二个循环从后遍历
            for (int x = height.length - 1; x > i; x--) {
                if (height[x] < height[i]) {
                    area = max(area, height[x] * (x - i));
                } else {
                    area = max(area, height[i] * (x - i));
                    break;
                }
            }
        }
        return area;
    }

    public static int maxArea(int[] height) {
        //初始化最大值
        int area = 0;
        //两个指针，一个指向前，一个指向后
        for (int x = 0, y = height.length - 1; x < y; ) {
            area = max(area, min(height[x], height[y]) * (y - x));
            //对比下然后移动较小的那个
            if (height[x] < height[y]) {
                x++;
            } else {
                y--;
            }
        }
        return area;
    }

    public static int max(int a, int b) {
        return a > b ? a : b;
    }

    public static int min(int a, int b) {
        return a < b ? a : b;
    }


}